점근 표기법

알고리즘의 계산복잡도 설명에 사용하는 표기법. $f(n)=O(n^2)$ 꼴로 쓴다.

On notation

$\mathrm{\Theta }(g(n))$ is a set:

“

Because $\mathrm{\Theta }(g(n))$ is a set, we could write " $f(n)\in \mathrm{\Theta }(g(n))$" to indicate that $f(n)$ is a member of $\mathrm{\Theta }(g(n))$. Instead, we will usually write " $f(n)=\mathrm{\Theta }(g(n))$" to express the same notion.¹

Minor abusing:

“

Since any constant is a degree-0 polynomial, we can express any constant function as $\mathrm{\Theta }(n^0)$, or $\mathrm{\Theta }(1)$. This latter notation is a minor abuse, however, becuase the expression doesn not indicate what variable is tending to infinity. We shall often use the notation $\mathrm{\Theta }(1)$ to mean either a constant or a constant function with respect to some variable.

(The real problem is that our ordinary notation for functions does not distinguish functions from values. in Lambda calculus, the parameters to a function are clealy specified: the function $n^2$ could be written as $\lambda n.n^2$, or even $\lambda r.r^2$. Adopting a more rigorous notation, howevery, would complicate algebraic manipulations, and so we choose to tolerate the abuse.)¹

$\mathrm{\Theta }$-notation (Big Theta notation)

정의:¹

“

For a given function $g(n),wedenoteby$\Theta(g(n))$ the set of functions.

$\mathrm{\Theta }(g(n))$ = { $f(n)$ such that there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$ for all $n\ge n_0$ .

설명:¹

“

A function $f(n)$ belongs to the set $\mathrm{\Theta }(g(n))$ if there exist positive constants $c_1$ and $c_2$ such that it can be “sandwiched” between $c_{1}g(n)$ and $c_{2}g(n)$, for sufficiently large $n$. … In other words, for all $n\ge n_0$, the function $f(n)$ is equal to $g(n)$ to within a constant factor. We say that $g(n)$ is an asymptotically tight bound for $f(n)$.

$\mathrm{\Omega }$-notation (Big Omega notation)

O-notation (Big O notation)

Footnotes

1. Chapter 3, Introduction to algorithms ^{2 3 4}